// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.


#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"

#define BUCKET 10

struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  /*
    将之前的LRU算法链表给换掉
    这个是导致速度被拖累的源泉
    因为每次的操作都是需要对该链表进行操作
  */
  struct buf hash_bucket[BUCKET]; // 桶链表，每个桶都是一个LRU
  struct spinlock hash_lock[BUCKET]; // 桶锁
} bcache;

static int check(struct buf* hash_bucket) {
  int sum = 0;
  for(int i = 0; i < BUCKET; i++) {
    for(struct buf* b = hash_bucket[i].next; b != &hash_bucket[i]; b = b->next) {
      sum++;
    }
  }
  return sum;
}

inline static int hash(uint dev, uint blockno) {
  return (dev + blockno) % BUCKET;
}

void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");

  // Create linked list of buffers
  // bcache.head.prev = &bcache.head;
  // bcache.head.next = &bcache.head;

  // 对LRU算法的list进行初始化
  // for(b = bcache.buf; b < bcache.buf+NBUF; b++){
  //   b->next = bcache.head.next;
  //   b->prev = &bcache.head;
  //   initsleeplock(&b->lock, "buffer");
  //   bcache.head.next->prev = b;
  //   bcache.head.next = b;
  // }

  for(int i = 0; i < BUCKET; i++) {
    bcache.hash_bucket[i].next = &bcache.hash_bucket[i];
    bcache.hash_bucket[i].prev = &bcache.hash_bucket[i];
  }

  // 将buf放到桶中
  for(b = bcache.buf; b < bcache.buf + NBUF; b++) {
    int index = hash(b->dev, b->blockno);

    // 头插法
    b->next = bcache.hash_bucket[index].next;
    bcache.hash_bucket[index].next->prev = b;
    bcache.hash_bucket[index].next = b;
    b->prev = &bcache.hash_bucket[index];
    
    b->valid = 0; // 无效
    b->refcnt = 0;
  }

  int sum;
  if((sum = check(bcache.hash_bucket)) != 30) {
    printf("init sum: %d\n", sum);
    panic("init出错");
  }

  printf("bio init成功\n");
}

// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;

  int sum;
  if((sum = check(bcache.hash_bucket)) != 30) {
    printf("sum: %d\n", sum);
    panic("桶链接出错！");
  }

  int index = hash(dev, blockno);
  acquire(&bcache.hash_lock[index]);

  for(b = bcache.hash_bucket[index].next; b != &bcache.hash_bucket[index]; b = b->next) {

    if(b->dev == dev && b->blockno == blockno) {
      b->refcnt++;
      release(&bcache.hash_lock[index]);
      acquiresleep(&b->lock); // 守护该块缓存
      return b;
    }
  }

  /*
    从该同中获取一个没空的buf
  */
  for(b = bcache.hash_bucket[index].next; b != &bcache.hash_bucket[index]; b = b->next) {
    if(b->refcnt == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;
      b->refcnt = 1;
      release(&bcache.hash_lock[index]);
      acquiresleep(&b->lock);
      return b;
    }
  }

  /*
    该桶没有可用的buf了，从别的桶借
    若是别的桶也没有合适的，就应该报错了
    
    我一开始写的for循环其实是有问题的，这么写很容易出错，建议换一种写法
  */
  // for(int i = index + 1; i != index; i++) {
  //   if(i >= BUCKET) { i %= BUCKET; i--; continue; }
  for(int i = (index + 1) % BUCKET; i != index; i = (i + 1) % BUCKET) {

    acquire(&bcache.hash_lock[i]);

    for(b = bcache.hash_bucket[i].next; b != &bcache.hash_bucket[i]; b = b->next) {
      if(b->refcnt == 0) {
        // 将这个buf换到index下

        b->next->prev = b->prev;
        b->prev->next = b->next;

        b->prev = &bcache.hash_bucket[index];
        b->next = bcache.hash_bucket[index].next;
        bcache.hash_bucket[index].next->prev = b;
        bcache.hash_bucket[index].next = b;

        
        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;

        release(&bcache.hash_lock[i]);
        release(&bcache.hash_lock[index]);
        acquiresleep(&b->lock);
        return b;
      }
    }

    release(&bcache.hash_lock[i]); // 这个锁千万不能忘记释放了，没释放就会死锁
  }

  // 没有一个buf是可用的
  panic("bget: no buffers");
}

// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if(!b->valid) {
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b, 1);
}

// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  int index = hash(b->dev, b->blockno);
  acquire(&bcache.hash_lock[index]);
  b->refcnt--;
  // if (b->refcnt == 0) {
  //   // no one is waiting for it.
  //   b->next->prev = b->prev;
  //   b->prev->next = b->next;
  //   b->next = bcache.head.next;
  //   b->prev = &bcache.head;
  //   bcache.head.next->prev = b;
  //   bcache.head.next = b;
  // }
  
  release(&bcache.hash_lock[index]);
}

void
bpin(struct buf *b) {
  acquire(&bcache.lock);
  b->refcnt++;
  release(&bcache.lock);
}

void
bunpin(struct buf *b) {
  acquire(&bcache.lock);
  b->refcnt--;
  release(&bcache.lock);
}


